This invention relates to connection based communications networks and more particularly to apparatus and methods for implementing virtual path aggregation while providing fair share arbitration between underlying virtual channel (VC) and/or virtual path (VP) connections.
Asynchronous transfer mode (ATM), as an example of connection based communications technology, is rapidly being recognized as the technology of choice for broadband data communications. ATM is a packet-based scheme in which the packets, known as cells, have a fixed number of bytes divided between the cell header and cell payload. ATM technology can efficiently accommodate different service categories thereby being well suited to deliver multimedia traffic such as video, voice and data.
ATM cell traffic between intermediate switching nodes in an ATM network is carried on what are known as virtual connections (VCs). Traffic from end user to end user through a plurality of intermediate nodes is carried on virtual channel connections (VCCs). Since traffic from several sources may have a common destination it is known to combine virtual channel connections onto a virtual path connection (VPC) in order to simplify the processing of traffic through the network. A VCC on a particular link is uniquely identified by the combination of virtual path identifier (VPI) and virtual channel identifier (VCI) fields in the ATM cell headers. A VPC on a particular link is uniquely identified by the VPI field in the ATM cell header. When virtual channel connections are aggregated onto a virtual path connection, the individual virtual channel connections are essentially transparent to the intermediate ATM nodes and this allows a simpler networking model and higher manageability.
A virtual path connection (VPC) is defined as a logical grouping of multiple virtual channel connections (VCCs) into one virtual connection. An implicit logical aggregation of VCCs into a VPC is said to have occurred when the outgoing VCCs all acquire the same common VPI value. Typically, such aggregation occurs at the egress port of an ATM switch where multiple VCCs from multiple ingress ports converge. These aggregating VCCs might have different VPI and VCI values as determined at call setup or network planning time. The egress port of the ATM switch is typically equipped with a cell header translation function. Such a function is capable of translating the incoming VPI and VCI values into a new set of VPI and VCI values. It is this function that accomplishes the aforementioned implicit logical aggregation. When the various VPI and VCI values on the various aggregating VCCs all translate into a common VPI value, a virtual path connection is formed. Note that the VCI value is carried transparently end-to-end within a VPC. It is, therefore, important for the translation function to translate the incoming VCI values into a mutually exclusive set of VCI values. Such mutual exclusivity allows each underlying VCC to be uniquely identified at the terminating end of the VPC. At that point, the VPC is segmented by simply switching and processing each underlying VCC as an individual connection. The combination of an egress aggregation function together with the ingress segregation function on a bi-directional port is referred to as the virtual path termination point (VPTP).
Although the aggregation of virtual channel connections onto a common path simplifies traffic management, concerns have been expressed that individual virtual channel connections may not all be treated fairly when aggregated onto a virtual path connection. Demirtjis and Petr (IEEE IC3N, 1995 xe2x80x9cHow to Encourage Cheating with Virtual Path Policing in ATM Networksxe2x80x9d) have found that virtual channel connections which are in compliance with predefined transmission parameters may be adversely affected by non-compliant traffic when aggregated onto a virtual path.
U.S. Pat. No. 5,629,928 which issued May 13, 1997 to Calvignac et al discloses one technique for controlling traffic flow in a virtual path communication system wherein queues allocated as needed from a pool of free queues are used to store all incoming data cells having the same virtual channel identifier.
U.S. patent application Ser. No. 09/200,444 filed Nov. 27, 1998 by Carr et al and assigned to Alcatek Canada Inc. now U.S. Pat. No. 6,643,295 discloses an apparatus and method for scheduling and shaping multi-service category cell traffic unto virtual path connections. The contents of U.S. Pat. No. 6,643,295 are incorporated herein by reference.
The present invention seeks to provide solutions to the problem of how to group the underlying VCs and/or VPs to form an aggregate-VP, and how to fairly select an underlying VC/VP to service.
The present invention provides a technique of representing and managing the Aggregated-VPs and underlying VCs. The invention also provides a technique of fairly selecting and keeping track of the next underlying VC that should be serviced.
Therefore, in accordance with a first broad aspect of the present invention there is provided in a digital communications network a method of aggregating multiple virtual circuits (VCs) to form an aggregate-virtual path comprising: creating a linked list to represent the aggregate virtual path and assigning each of the VCs to an element in the linked list.
In a preferred embodiment the linked list is a circular linked list. Further, the aggregate virtual path will consist of a group of such circular linked lists with individual linked lists allocated in accordance with traffic descriptors.
In accordance with a further broad aspect of the invention there is provided a device for aggregating virtual circuits in a digital communications network into aggregate virtual paths, the device comprising: means to create a linked list associated with each aggregate virtual path, and means to assign each virtual circuit to an element in the linked list.
In a preferred embodiment of this aspect of the invention a group of circular linked lists will be created. Further, the device will include means to add or remove each virtual circuit to or from one of the circular linked lists.
The invention advantageously provides arbitration of the individual VCs at their aggregation into a VP (VPA) whereby conformance of that VP connection to its traffic descriptor is ensured within the network core.